#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

#include "TypeDefin.h"

using namespace std;

// ___
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

    if (preorder.empty() || inorder.empty())
        return nullptr;

    auto root = new TreeNode(preorder[0]);

    vector<int> inorder_left;
    vector<int> inorder_right;

    for (int i = 0; i < inorder.size(); i++) {

        if (inorder[i] == preorder[0]) {
            inorder_right.assign(inorder.begin() + i + 1, inorder.end());
            break;
        } else {
            inorder_left.push_back(inorder[i]);
        }
    }
    vector<int> pre_left(preorder.begin() + 1, preorder.begin() + 1 + inorder_left.size());
    vector<int> pre_right(preorder.begin() + 1 + inorder_left.size(), preorder.end());

    root->left = buildTree(pre_left, inorder_left);
    root->right = buildTree(pre_right, inorder_right);


    return root;

}
